package com.squirrel.michale;

import java.util.*;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/10 1:51 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0358 {


    public String rearrangeString(String str, int k) {
        if (k == 0) {
            return str;
        }
        // 1.构建单词与频率的映射
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch ,map.get(ch) + 1);
            } else {
                map.put(ch, 1);
            }
        }
        // 2.将所有出现的字母按照频率排序
        PriorityQueue<Character> queue = new PriorityQueue<>((c1, c2) -> {
            if (map.get(c2).intValue() != map.get(c1).intValue()) {
                return map.get(c2) - map.get(c1);
            } else {
                // 如果频率相同，按字典排序
                return c1.compareTo(c2);
            }
        });
        // 把字符放入队列,频率大的在前面
        for (char c: map.keySet()) {
            queue.offer(c);
        }
        // 试图构建字符串
        StringBuilder sb = new StringBuilder();
        // 初始字符长度
        int len = str.length();
        // 3. 把字符按出现次数多的字符开始，把每一个字符插入到间隔中
        while (!queue.isEmpty()) {
            List<Character> tempChars = new ArrayList<>();
            // 得到较小的数（最后剩下的一截可能不够K）
            int n = Math.min(k, len);
            // 从queue里取出TopN位数字，填充每一个间隔区间
            for (int i = 0; i < n; i++) {
                // 在个数为N的间隔区间里，剩下的不重复的字符串已经用完了,那么必然构造不出间隔为N的无重复字符串了，
                // 也就是在这个区间里必然有重复的字母，到这里就无法再继续构造了
                if (queue.isEmpty()) {
                    return "";
                }
                // 取出这个字符
                char ch = queue.poll();
                sb.append(ch);
                // 取出这个字符，相应频次要减1
                map.put(ch, map.get(ch) - 1);
                // 这个字符还有剩余,就加进来tempChars，重新放到queue里，进行下一次的遍历
                if (map.get(ch) > 0) {
                    tempChars.add(ch);
                }
                // 已经取过了，字符长度减1
                len--;
            }

            // 4.每个字母减过一次了，把还有剩余次数的字母再次加入到queue里，继续下一次的循环
            for (Character tempChar : tempChars) {
                queue.offer(tempChar);
            }
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        LeetCode0358 solution = new LeetCode0358();
        String res = solution.rearrangeString("aabbcc", 3);
        String res2 = solution.rearrangeString("aaabc", 3);
        String res3 = solution.rearrangeString("aaadbbcc", 2);
        System.out.println(res);
        System.out.println(res2);
        System.out.println(res3);
    }

}
